package srcLongestCommonSubsequence;

public class LCSCalculator
{
    public static void main(String[] args)
    {
        String firstSequence = "BARTHOLEMEWSIMPSON";
        String secondSequence = "KRUSTYTHECLOWN";


        LCSCalculator h = new LCSCalculator();

        String lcs = h.GetLCSUsingDivideAndConquer(firstSequence.length(), secondSequence.length(), firstSequence, secondSequence);

        System.out.println(
                String.format(
                        "LCS of \n%s \n%s \nIS \n%s",
                        firstSequence,
                        secondSequence,
                        lcs));

    }

    /**
     * Reverses given string
     * @param s
     * @return reversed string s
     */
    private static String ReverseString(String s)
    {
        StringBuffer buf = new StringBuffer(s);
        return buf.reverse().toString();
    }

    /**
     * Computes length of longest common subsequence,
     * by traversing the strings from start to end,
     * in space efficient fashion i.e O(n) space
     * @param firstStringLength
     * @param secondStringLength
     * @param firstString
     * @param secondString
     * @return Length of longest common subsequence
     */
    private int[] ComputeLCSForwardsUsingSpaceEfficientAlgo(
            int firstStringLength,
            int secondStringLength,
            String firstString,
            String secondString)
    {
        int[][] M = new int[2][secondStringLength + 1];

        for (int j = 0; j <= secondStringLength; j++)
        {
                M[0][j] = 0;
        }

        for (int i=1; i <= firstStringLength; i++)
        {
            for (int j=1; j <= secondStringLength; j++)
            {
                    if(firstString.charAt(i-1) == secondString.charAt(j-1))
                    {
                            M[1][j] = M[0][j-1] + 1;
                    }
                    else
                    {
                            M[1][j] = Math.max(M[1][j-1], M[0][j]);
                    }
            }

            // move values from M[0] to M[1] to make space for next iteration
            for (int j=0; j <= secondStringLength; j++)
            {
                    M[0][j] = M[1][j];
            }
        }

        return M[1];
    }

    /**
     * Computes LCS of two strings starting from backwards.
     * Basically reverses the strings and calls the forward LCS computation method.
     * @param firstStringLength
     * @param secondStringLength
     * @param firstString
     * @param secondString
     * @return
     */
    private int[] ComputeLCSBackwardsUsingSpaceEfficientAlgo(
            int firstStringLength,
            int secondStringLength,
            String firstString,
            String secondString)
    {
        return ComputeLCSForwardsUsingSpaceEfficientAlgo(
                firstStringLength,
                secondStringLength,
                ReverseString(firstString),
                ReverseString(secondString));
    }

    /**
     * Uses divide and conquer + dynamic programming to return longest common subsequence
     * in linear space
     * @param firstStringLength
     * @param secondStringLength
     * @param firstString
     * @param secondString
     * @return longest common subsequence
     */
    public String GetLCSUsingDivideAndConquer(
            int firstStringLength,
            int secondStringLength,
            String firstString,
            String secondString)
    {
        String lcs = "";

        if (secondStringLength == 0)
        {
            lcs = "";
        }
        else if (firstStringLength == 1)
        {
            for(int j = 0; j < secondStringLength; j++)
            {
                if (firstString.charAt(0)==secondString.charAt(j))
                {
                    lcs = Character.toString(firstString.charAt(0));
                    break;
                }
                else
                {
                    lcs = "";
                }
            }
        }
        else
        {
            int firstStringMid= firstStringLength / 2;

            int[] leftColumn = ComputeLCSForwardsUsingSpaceEfficientAlgo(
                    firstStringMid,
                    secondStringLength,
                    firstString.substring(0, firstStringMid),
                    secondString);

            int[] rightColumn = ComputeLCSBackwardsUsingSpaceEfficientAlgo(
                    firstStringLength - firstStringMid,
                    secondStringLength,
                    firstString.substring(firstStringMid),
                    secondString);

            int maximizingIndex = GetMaximizingIndex(leftColumn, rightColumn, secondStringLength);

            String leftLCS = GetLCSUsingDivideAndConquer(
                    firstStringMid,
                    maximizingIndex,
                    firstString.substring(0, firstStringMid),
                    secondString.substring(0, maximizingIndex));

            String rightLCS = GetLCSUsingDivideAndConquer(
                    firstStringLength - firstStringMid,
                    secondStringLength - maximizingIndex,
                    firstString.substring(firstStringMid),
                    secondString.substring(maximizingIndex));

            lcs = leftLCS + rightLCS;
        }

        return lcs;
    }

    /**
     * Merges appropriate values of the left and right column obtained by the divide and conquer algorithm
     * @param leftColumn
     * @param rightColumn
     * @param numberOfEntries
     * @return index of the entry that maximizes the sum of left and right column
     */
    private int GetMaximizingIndex(int[] leftColumn, int[] rightColumn, int numberOfEntries)
    {
        int maxSum = 0;
        int maxSumIndex = 0;

        for (int j=0; j <= numberOfEntries; j++)
        {
            int curSum = leftColumn[j] + rightColumn[numberOfEntries - j];
            if (maxSum < curSum)
            {
                maxSum = curSum;
                maxSumIndex = j;
            }
        }

        return maxSumIndex;
    }
}
